# Python中表示二叉树的几种常见方法

"""
二叉树是每个节点最多有两个子节点的树结构，通常称为左子节点和右子节点。
Python中有多种方式可以表示二叉树结构，每种方式都有其适用场景。
"""

# 示例二叉树：
#       1
#      / \
#     2   3
#    /   / \
#   4   5   6

# 1. 节点类表示法（最常用）
print("1. 节点类表示法")

class TreeNode:
    """二叉树节点类（支持多种数据类型）"""
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 构建示例二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)

# 遍历方法
def preorder_traversal(root):
    """前序遍历：根 -> 左 -> 右"""
    if not root:
        return []
    return [root.val] + preorder_traversal(root.left) + preorder_traversal(root.right)

def inorder_traversal(root):
    """中序遍历：左 -> 根 -> 右"""
    if not root:
        return []
    return inorder_traversal(root.left) + [root.val] + inorder_traversal(root.right)

def postorder_traversal(root):
    """后序遍历：左 -> 右 -> 根"""
    if not root:
        return []
    return postorder_traversal(root.left) + postorder_traversal(root.right) + [root.val]

print(f"前序遍历: {preorder_traversal(root)}")
print(f"中序遍历: {inorder_traversal(root)}")
print(f"后序遍历: {postorder_traversal(root)}")
print()

# 2. 列表表示法（LeetCode常用）
print("2. 列表表示法")
# 使用None表示空节点，按层次遍历顺序存储
binary_tree_list = [1, 2, 3, 4, None, 5, 6, None, None, None, None, None, None]

def build_tree_from_list(lst):
    """从列表构建二叉树"""
    if not lst:
        return None
    
    nodes = [TreeNode(val) if val is not None else None for val in lst]
    
    for i in range(len(lst)):
        if nodes[i] is not None:
            left_index = 2 * i + 1
            right_index = 2 * i + 2
            
            if left_index < len(lst) and nodes[left_index] is not None:
                nodes[i].left = nodes[left_index]
            if right_index < len(lst) and nodes[right_index] is not None:
                nodes[i].right = nodes[right_index]
    
    return nodes[0]

# 从列表构建树
tree_from_list = build_tree_from_list(binary_tree_list)
print(f"从列表构建的树的前序遍历: {preorder_traversal(tree_from_list)}")
print()

# 3. 字典表示法（适合序列化和反序列化）
print("3. 字典表示法")
tree_dict = {
    'val': 1,
    'left': {
        'val': 2,
        'left': {
            'val': 4,
            'left': None,
            'right': None
        },
        'right': None
    },
    'right': {
        'val': 3,
        'left': {
            'val': 5,
            'left': None,
            'right': None
        },
        'right': {
            'val': 6,
            'left': None,
            'right': None
        }
    }
}

def dict_to_tree(data):
    """从字典构建二叉树"""
    if data is None:
        return None
    return TreeNode(
        data['val'],
        dict_to_tree(data['left']),
        dict_to_tree(data['right'])
    )

def tree_to_dict(root):
    """二叉树转换为字典"""
    if root is None:
        return None
    return {
        'val': root.val,
        'left': tree_to_dict(root.left),
        'right': tree_to_dict(root.right)
    }

tree_from_dict = dict_to_tree(tree_dict)
print(f"从字典构建的树的中序遍历: {inorder_traversal(tree_from_dict)}")
print(f"树转换为字典: {tree_to_dict(root)}")
print()

# 4. 嵌套元组表示法
print("4. 嵌套元组表示法")
# 格式: (根节点值, 左子树, 右子树)
tree_tuple = (1, (2, (4, None, None), None), (3, (5, None, None), (6, None, None)))

def tuple_to_tree(tup):
    """从元组构建二叉树"""
    if tup is None:
        return None
    if isinstance(tup, tuple) and len(tup) == 3:
        val, left, right = tup
        return TreeNode(val, tuple_to_tree(left), tuple_to_tree(right))
    elif isinstance(tup, (int, float, str)):
        return TreeNode(tup)
    return None

def tree_to_tuple(root):
    """二叉树转换为元组"""
    if root is None:
        return None
    left_tuple = tree_to_tuple(root.left)
    right_tuple = tree_to_tuple(root.right)
    return (root.val, left_tuple, right_tuple)

tree_from_tuple = tuple_to_tree(tree_tuple)
print(f"从元组构建的树的后序遍历: {postorder_traversal(tree_from_tuple)}")
print(f"树转换为元组: {tree_to_tuple(root)}")
print()

# 5. 二叉搜索树（BST）表示法
print("5. 二叉搜索树表示法")

class BSTNode:
    """二叉搜索树节点"""
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def insert_bst(root, val):
    """向BST插入节点"""
    if root is None:
        return BSTNode(val)
    
    if val < root.val:
        root.left = insert_bst(root.left, val)
    else:
        root.right = insert_bst(root.right, val)
    
    return root

def search_bst(root, val):
    """在BST中搜索值"""
    if root is None or root.val == val:
        return root
    
    if val < root.val:
        return search_bst(root.left, val)
    else:
        return search_bst(root.right, val)

# 构建二叉搜索树
bst_root = None
for val in [5, 3, 7, 2, 4, 6, 8]:
    bst_root = insert_bst(bst_root, val)

print(f"BST中序遍历（应该是有序的）: {inorder_traversal(bst_root)}")
print(f"搜索值4: {search_bst(bst_root, 4) is not None}")
print(f"搜索值9: {search_bst(bst_root, 9) is not None}")
print()

# 6. 使用第三方库（如binarytree）
print("6. 使用第三方库")
try:
    from binarytree import Node, build
    
    # 使用binarytree库构建二叉树
    try:
        bt_root = Node(1)
        bt_root.left = Node(2)
        bt_root.right = Node(3)
        bt_root.left.left = Node(4)
        bt_root.right.left = Node(5)
        bt_root.right.right = Node(6)
        
        print("binarytree库构建的树:")
        print(bt_root)
        
        # 从列表构建
        values = [1, 2, 3, 4, None, 5, 6]
        bt_tree = build(values)
        print("从列表构建的树:")
        print(bt_tree)
    except Exception as e:
        print(f"binarytree库使用出错: {e}")
    
except ImportError:
    print("请安装binarytree库: pip install binarytree")
    print("或者使用其他方法表示二叉树")

# 7. 层次遍历表示法
print("\n7. 层次遍历表示法")

def level_order_traversal(root):
    """层次遍历二叉树"""
    if not root:
        return []
    
    result = []
    queue = [root]
    
    while queue:
        node = queue.pop(0)
        result.append(node.val)
        
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    
    return result

print(f"层次遍历结果: {level_order_traversal(root)}")

# 工具函数：可视化二叉树（ASCII艺术）
def print_tree(root, level=0, prefix="Root: "):
    """打印二叉树结构"""
    if root is not None:
        print(" " * (level * 4) + prefix + str(root.val))
        if root.left is not None:
            print_tree(root.left, level + 1, "L--- ")
        if root.right is not None:
            print_tree(root.right, level + 1, "R--- ")

print("\n二叉树结构:")
print_tree(root)